Почему он всё-таки сходится

Стохастический Градиентный Спуск (SGD) имеет достаточно простую запись:

xk+1=xkαkgk.x_{k+1} = x_k - \alpha_k g_k.

Здесь gkg_k — это некоторая аппроксимация градиента целевой функции f(xk)\nabla f(x_k) в точке xkx_k, называемая стохастическим градиентом (или просто стох. градиентом), αk>0\alpha_k > 0 — это размер шага (stepsize, learning rate) на итерации kk. Для простоты мы будем считать, что αk=α>0\alpha_k = \alpha > 0 для всех k0k \geq 0. Обычно предполагается, что стох. градиент является несмещённой оценкой f(xk)\nabla f(x_k) при фиксированном xkx_k: E(gkxk)=f(xk)\mathbb{E}\left(g_k \mid x_k\right) = \nabla f(x_k).

Доказательство сходимости

Зададимся следующим вопросом: с какой скоростью и в каком смысле SGD сходится к решению и сходится ли? Во-первых, как и во многих работах по стохастической оптимизации, нас будет интересовать сходимость метода в среднем, т.е. оценки на E(14xkx2)\mathbb{E}\left(\vphantom{\frac14}\vert\vert x_k - x_\ast\vert\vert^2\right) или E(f(xk)f(x))\mathbb{E}\left(f(x_k) - f(x_\ast)\right), где xx_\ast — решение задачи (для простоты будем считать, что оно единственное).

Во-вторых, чтобы SGD сходился в указанном смысле, необходимо ввести дополнительные предположения. Действительно, например, если дисперсия стох. градиента не ограничена E(14gkf(xk)2xk)=\mathbb{E}\left(\vphantom{\frac14}\vert\vert g_k - \nabla f(x_k)\vert\vert^2 \mid x_k\right) = \infty, то E(14xkx2)=\mathbb{E}\left(\vphantom{\frac14}\vert\vert x_k - x_\ast\vert\vert^2\right) = \infty и никаких разумных гарантий доказать не удаётся. Поэтому дополнительно к несмещённости часто предполагается, что дисперсия равномерно ограничена: предположим, что существует такое число σ0\sigma \ge 0, что для всех k0k \ge 0 выполнено

Вступайте в сообщество хендбука

Здесь можно найти единомышленников, экспертов и просто интересных собеседников. А ещё — получить помощь или поделиться знаниями.

E(14gkf(xk)2xk)σ2.\mathbb{E}\left(\left.\vphantom{\frac14}\vert\vert g_k - \nabla f(x_k)\vert\vert^2\right| x_k\right) \leq \sigma^2.

Данное предположение выполнено, например, для задачи логистической регрессии (поскольку в данной задаче норма градиентов слагаемых ограничена), но в то же время является весьма обременительным. Его можно заменить на более реалистичные предположения, что мы немного затронем далее. Однако при данном предположении анализ SGD является очень простым и полезным для дальнейших обобщений и рассуждений.

Для простоты везде далее мы будем считать, что функция ff является LL-гладкой и μ\mu-сильно выпуклой, т.е. для всех x,yRdx, y \in \mathbb{R}^d выполнены неравенства

f(x)f(y)Lxy, \vert\vert\nabla f(x) - \nabla f(y)\vert\vert \leq L\vert\vert x-y\vert\vert,

f(y)f(x)+f(x),yx+μ2yx2. f(y) \geq f(x) + \langle\nabla f(x), y- x \rangle + \frac{\mu}{2}\vert\vert y - x\vert\vert^2.

Теорема. Предположим, что ff является LL-гладкой и μ\mu-сильно выпуклой, стох. градиент gkg_k имеет ограниченную дисперсию, и размер шага удовлетворяет 0<α1/L0 < \alpha \leq 1/L. Тогда для всех k0k \geq 0 выполняется неравенство

E(14xkx2)(1αμ)kx0x2+ασ2μ. \mathbb{E}\left(\vphantom{\frac14}\vert\vert x_k - x_{\ast}\vert\vert^2\right) \leq (1 - \alpha\mu)^k\vert\vert x_0 - x_{\ast}\vert\vert^2 + \frac{\alpha\sigma^2}{\mu}.

Доказательство. Используя выражение для xk+1x_{k+1}, мы выводим

xk+1x2=xkxαgk2=xkx22αxkx,gk+α2gk2\vert\vert x_{k+1} - x_\ast \vert\vert^2 = \vert\vert x_k - x_{\ast} - \alpha g_k\vert\vert^2\\ = \vert\vert x_k - x_{\ast}\vert\vert^2 - 2\alpha \langle x_k - x_{\ast}, g_k \rangle + \alpha^2 \vert\vert g_k\vert\vert^2

Далее мы берём условное матожидание E(xk)\mathbb{E}\left(\cdot\mid x_k\right) от левой и правой частей и получаем:

E(14xk+1x2xk)=xkx22αE(xkx,gkxk)+α2E(14gk2xk)=xkx22αxkx,E(gkxk)+α2E(14gk2xk)=xkx22αxkx,f(xk)+α2E(14gk2xk). \mathbb{E}\left(\left.\vphantom{\frac14}\vert\vert x_{k+1} - x_\ast\vert\vert^2\right| x_k\right) = \vert\vert x_k - x_{\ast}\vert\vert^2 - 2\alpha\mathbb{E}\left( \langle x_k - x_{\ast}, g_k \rangle \mid x_k\right) + \alpha^2 \mathbb{E}\left(\left.\vphantom{\frac14}\vert\vert g_k\vert\vert^2\right| x_k\right)\\ = \vert\vert x_k - x_{\ast}\vert\vert^2 - 2\alpha\left\langle x_k - x_{\ast}, \mathbb{E}\left(g_k \mid x_k\right) \right\rangle + \alpha^2 \mathbb{E}\left(\left.\vphantom{\frac14}\vert\vert g_k\vert\vert^2\right| x_k\right)\\ = \vert\vert x_k - x_{\ast}\vert\vert^2 - 2\alpha\langle x_k - x_{\ast}, \nabla f(x_k)\rangle + \alpha^2 \mathbb{E}\left(\left.\vphantom{\frac14}\vert\vert g_k\vert\vert^2\right| x_k\right).

Следующий шаг в доказательстве состоит в оценке второго момента E(14gk2xk)\mathbb{E}\left(\vphantom{\frac14}\vert\vert g_k\vert\vert^2 \mid x_k\right). Используя предположение об ограниченности дисперсии стох. градиента, мы выводим:

E(14gk2xk)=E(14f(xk)+gkf(xk)2xk)=f(xk)2+E(f(xk),gkf(xk)xk)+E(14gkf(xk)2xk)=f(xk)2+f(xk),E(gkf(xk)xk)+E(14gkf(xk)2xk)=f(xk)2+E(14gkf(xk)2xk)f(xk)2+σ2 \mathbb{E}\left(\left.\vphantom{\frac14}\vert\vert g_k\vert\vert^2\right| x_k\right) = \mathbb{E}\left(\left.\vphantom{\frac14}\vert\vert\nabla f(x_k) + g_k - \nabla f(x_k)\vert\vert^2\right| x_k\right)\\ = \vert\vert\nabla f(x_k)\vert\vert^2 + \mathbb{E}\left(\langle \nabla f(x_k), g_k - \nabla f(x_k) \rangle \mid x_k\right) + \mathbb{E}\left(\left.\vphantom{\frac14}\vert\vert g_k - \nabla f(x_k)\vert\vert^2 \right| x_k\right)\\ = \vert\vert\nabla f(x_k)\vert\vert^2 + \left\langle \nabla f(x_k), \mathbb{E}\left(g_k - \nabla f(x_k) \mid x_k\right)\right\rangle + \mathbb{E}\left(\left.\vphantom{\frac14}\vert\vert g_k - \nabla f(x_k)\vert\vert^2 \right| x_k\right)\\ = \vert\vert\nabla f(x_k)\vert\vert^2 + \mathbb{E}\left(\left.\vphantom{\frac14}\vert\vert g_k - \nabla f(x_k)\vert\vert^2 \right| x_k\right)\\ \leq \vert\vert\nabla f(x_k)\vert\vert^2 + \sigma^2

Чтобы оценить сверху f(xk)2\vert\vert\nabla f(x_k)\vert\vert^2, мы используем следующий факт, справедливый для любой выпуклой LL-гладкой функции ff (см. книгу Ю. Е. Нестерова "Методы выпуклой оптимизации", 2010):

f(x)f(y)22L(f(x)f(y)f(y),xy). \vert\vert\nabla f(x) - \nabla f(y)\vert\vert^2 \leq 2L\left(f(x) - f(y) - \langle \nabla f(y), x- y \rangle\right).

Беря в этом неравенстве x=xkx = x_k, y=xy = x_\ast и используя f(x)=0\nabla f(x_\ast) = 0, получаем

E(14gk2xk)2L(f(xk)f(x))+σ2. \mathbb{E}\left(\left.\vphantom{\frac14}\vert\vert g_k\vert\vert^2\right| x_k\right) \leq 2L\left(f(x_k) - f(x_\ast)\right) + \sigma^2.

Далее мы подставляем эту оценку в выражение для E(xk+1x2xk)\mathbb{E}\left(\vert\vert x_{k+1} - x_\ast\vert\vert^2 \mid x_k\right):

E(14xk+1x2xk)xkx22αxkx,f(xk)+2α2L(f(xk)f(x))+α2σ2. \mathbb{E}\left(\left.\vphantom{\frac14}\vert\vert x_{k+1} - x_\ast\vert\vert^2\right| x_k\right) \leq \vert\vert x_k - x_{\ast}\vert\vert^2 - 2\alpha\langle x_k - x_{\ast}, \nabla f(x_k)\rangle + 2\alpha^2L\left(f(x_k) - f(x_\ast)\right) + \alpha^2\sigma^2.

Остаётся оценить скалярное произведение в правой части неравенства. Это можно сделать, воспользовавшись сильной выпуклостью функции ff: из

f(x)f(xk)+f(xk),xxk+μ2xxk2 f(x_\ast) \geq f(x_k) + \langle\nabla f(x_k), x_\ast - x_k \rangle + \frac{\mu}{2}\vert\vert x_\ast - x_k\vert\vert^2

следует

f(xk),xkxf(xk)f(x)+μ2xkx2. \langle\nabla f(x_k), x_k - x_\ast \rangle \geq f(x_k) - f(x_\ast) + \frac{\mu}{2}\vert\vert x_k - x_\ast\vert\vert^2.

Используя это неравенство в выведенной ранее верхней оценке на E(xk+1x2xk)\mathbb{E}\left(\vert\vert x_{k+1} - x_\ast\vert\vert^2\mid x_k\right), мы приходим к следующему неравенству:

E(14xk+1x2xk)(1αμ)xkx22α(1αL)(f(xk)f(x))+α2σ2(1αμ)xkx2+α2σ2, \mathbb{E}\left(\left.\vphantom{\frac14}\vert\vert x_{k+1} - x_\ast\vert\vert^2\right| x_k\right) \leq (1-\alpha\mu)\vert\vert x_k - x_{\ast}\vert\vert^2 -2\alpha(1 - \alpha L)\left(f(x_k) - f(x_\ast)\right) + \alpha^2\sigma^2\\ \leq (1-\alpha\mu)\vert\vert x_k - x_{\ast}\vert\vert^2 + \alpha^2\sigma^2,

где в последнем неравенстве мы воспользовались неотрицательностью 2α(1αL)(f(xk)f(x))2\alpha(1 - \alpha L)\left(f(x_k) - f(x_\ast)\right), что следует из 0<α1/L0 < \alpha \leq 1/L и f(xk)f(x)f(x_k) \geq f(x_\ast). Чтобы получить результат, заявленный в теореме, нужно взять полное мат. ожидание от левой и правой частей полученного неравенства (воспользовавшись при этом крайне полезным свойством условного мат. ожидания — tower property: E(E(xk))=E()\mathbb{E}\left(\mathbb{E}\left(\cdot\mid x^k\right)\right) = \mathbb{E}\left(\cdot\right))

E(14xk+1x2)(1αμ)E(14xkx2)+α2σ2, \mathbb{E}\left(\vphantom{\frac14}\vert\vert x_{k+1} - x_\ast\vert\vert^2\right) \leq (1-\alpha\mu)\mathbb{E}\left(\vphantom{\frac14}\vert\vert x_k - x_{\ast}\vert\vert^2\right) + \alpha^2\sigma^2,

а затем, применяя это неравенство для E(14xkx2)\mathbb{E}\left(\vphantom{\frac14}\vert\vert x_k - x_{\ast}\vert\vert^2\right), E(14xk1x2)\mathbb{E}\left(\vphantom{\frac14}\vert\vert x_{k-1} - x_{\ast}\vert\vert^2\right), \ldots , E(14x1x2)\mathbb{E}\left(\vphantom{\frac14}\vert\vert x_1 - x_{\ast}\vert\vert^2\right), получим

E(14xk+1x2)(1αμ)k+1x0x2+α2σ2t=0k(1αμ)t(1αμ)k+1x0x2+α2σ2t=0(1αμ)t=(1αμ)k+1x0x2+ασ2μ,\mathbb{E}\left(\vphantom{\frac14}\vert\vert x_{k+1} - x_\ast\vert\vert^2\right) \leq (1-\alpha\mu)^{k+1}\vert\vert x_0 - x_{\ast}\vert\vert^2 + \alpha^2\sigma^2\sum\limits_{t=0}^k (1-\alpha\mu)^t\\ \leq (1-\alpha\mu)^{k+1}\vert\vert x_0 - x_{\ast}\vert\vert^2 + \alpha^2\sigma^2\sum\limits_{t=0}^\infty (1-\alpha\mu)^t\\ = (1 - \alpha\mu)^{k+1}\vert\vert x_0 - x_{\ast}\vert\vert^2 + \frac{\alpha\sigma^2}{\mu},

что и требовалось доказать.

Данный результат утверждает, что SGD с потоянным шагом сходится линейно к окрестности решения, радиус которой пропорционален ασμ\tfrac{\sqrt{\alpha} \sigma}{\sqrt{\mu}}. Отметим, что чем больше размер шага α\alpha, тем быстрее SGD достигает некоторой окрестности решения, в которой продолжает осциллировать. Однако чем больше размер шага, тем больше эта окрестность. Соответственно, чтобы найти более точное решение, необходимо уменьшать размер шага в SGD. Этот феномен хорошо проиллюстрирован здесь.

Теорема выше доказана при достаточно обременительных предположениях: мы предположили, что функция является сильно выпуклой, LL-гладкой и стох. градиент имеет равномерно ограниченную дисперсию. В практически интересных задачах данные условия (в данном виде) выполняются крайне редко. Тем не менее, выводы, которые мы сделали из доказанной теоремы, справедливы для многих задач, не удовлетворяющих введённым предположениям (во многом потому, что указанные свойства важны лишь на некотором компакте вокруг решения задачи, что в свою очередь не так и обременительно).

Более того, если мы сделаем немного другое предположение о стохастических градиентах, то сможем покрыть некоторые случаи, когда дисперсия не является равномерно ограниченной на всём пространстве. Предположим теперь, что gk=fξk(xk)g_k = \nabla f_{\xi_k}(x_k), где ξk\xi_k просэмплировано из некоторого распределения D\cal D независимо от предыдущих итераций, f(x)=EξD(fξ(x))f(x) = \mathbb{E}_{\xi\sim \cal D}\left(f_{\xi}(x)\right) и fξ(x)f_{\xi}(x) является выпуклой и LξL_{\xi}-гладкой для всех ξ\xi (данное предположение тоже можно ослабить, но для простоты изложения остановимся именно на такой формулировке). Будем называть данные условия предположением о выпуклых гладких стохастчиеских реализациях. Они выполнены, например, для задач линейно регрессии и логистической регрессии.

В таком случае, для точек, сгенерированных SGD, справедливо, что SGD с потоянным шагом сходится линейно к окрестности решения, радиус которой пропорционален ασμ\tfrac{\sqrt{\alpha} \sigma}{\sqrt{\mu}}. Отметим, что чем больше размер шага α\alpha, тем быстрее SGD достигает некоторой окрестности решения, в которой продолжает осциллировать. Однако чем больше размер шага, тем больше эта окрестность. Соответственно, чтобы найти более точное решение, необходимо уменьшать размер шага в SGD. Этот феномен хорошо проиллюстрирован здесь.

Теорема. Предположим, что ff является LL-гладкой и μ\mu-сильно выпуклой, стохастчиеские реализации являются выпуклыми и гладкими, и размер шага удовлетворяет 0<α1/2Lmax0 < \alpha \leq 1/2L_{\max}, где Lmax=maxξDLξL_{\max} = \max_{\xi\sim \cal D} L_{\xi}. Тогда для всех k0k \geq 0 выполняется неравенство

E(14xkx2)(1αμ)kx0x2+2ασ2μ, \mathbb{E}\left(\vphantom{\frac14}\vert\vert x_k - x_{\ast}\vert\vert^2\right) \leq (1 - \alpha\mu)^k\vert\vert x_0 - x_{\ast}\vert\vert^2 + \frac{2\alpha\sigma_\ast^2}{\mu},

где σ2=EξDfξ(x)2\sigma_\ast^2 = \mathbb{E}_{\xi\sim \cal D}\vert\vert\nabla f_{\xi}(x_\ast)\vert\vert^2.

Доказательство. Аналогично предыдущей доказательству предыдущей теоремы, получаем

E(14xk+1x2xk)=xkx22αxkx,f(xk)+α2E(14gk2xk). \mathbb{E}\left(\left.\vphantom{\frac14}\vert\vert x_{k+1} - x_\ast\vert\vert^2\right| x_k\right) = \vert\vert x_k - x_{\ast}\vert\vert^2 - 2\alpha\langle x_k - x_{\ast}, \nabla f(x_k)\rangle + \alpha^2 \mathbb{E}\left(\left.\vphantom{\frac14}\vert\vert g_k\vert\vert^2\right| x_k\right).

Поскольку fξ(x)f_{\xi}(x) является выпуклой и LξL_\xi-гладкой, имеем (см. книгу Ю. Е. Нестерова "Методы выпуклой оптимизации", 2010):

fξ(x)fξ(y)22Lξ(fξ(x)fξ(y)fξ(y),xy). \vert\vert\nabla f_{\xi}(x) - \nabla f_{\xi}(y)\vert\vert^2 \leq 2L_{\xi}\left(f_{\xi}(x) - f_{\xi}(y) - \langle \nabla f_{\xi}(y), x - y \rangle\right).

Применяя это неравенство для x=xkx = x_k, y=xy = x_{\ast}, получаем

E(14gk2xk)=EξkD(fξk(xk)fξk(x)+fξk(x)2)2EξkD(fξk(xk)fξk(x)2)+2EξkD(fξk(x)2)EξkD(4Lξk(fξk(xk)fξk(x)fξk(x),xkx))+2EξD(fξk(x)2)4Lmax(f(xk)f(x)f(x),xkx)+2σ2=4Lmax(f(xk)f(x))+2σ2, \mathbb{E}\left(\left.\vphantom{\frac14}\vert\vert g_k\vert\vert^2\right| x_k\right) = \mathbb{E}_{\xi_k \sim \mathcal{D}}\left(\vert\vert\nabla f_{\xi_k}(x_k) - \nabla f_{\xi_k}(x_\ast) + \nabla f_{\xi_k}(x_\ast)\vert\vert^2\right)\\ \leq 2\mathbb{E}_{\xi_k \sim \mathcal{D}}\left(\vert\vert\nabla f_{\xi_k}(x_k) - \nabla f_{\xi_k}(x_\ast)\vert\vert^2\right) + 2\mathbb{E}_{\xi_k \sim \mathcal{D}}\left(\vert\vert\nabla f_{\xi_k}(x_\ast)\vert\vert^2\right)\\ \leq \mathbb{E}_{\xi_k \sim \mathcal{D}}\left(4L_{\xi_k}\left(f_{\xi_k}(x_k) - f_{\xi_k}(x_\ast) - \langle \nabla f_{\xi_k}(x_\ast), x_k - x_\ast \rangle\right)\right) + 2\mathbb{E}_{\xi \sim \mathcal{D}}\left(\vert\vert\nabla f_{\xi_k}(x_\ast)\vert\vert^2\right)\\ \leq 4L_{\max} \left(f(x_k) - f(x_\ast) - \langle \nabla f(x_\ast), x_k - x_\ast\rangle\right) + 2\sigma_{\ast}^2 \\ = 4L_{\max} \left(f(x_k) - f(x_\ast)\right) + 2\sigma_{\ast}^2,

где во втором переходе мы воспользовались стандартным фактом: a+b2a2+b2\vert\vert a+b\vert\vert^2 \leq \vert\vert a\vert\vert^2 + \vert\vert b\vert\vert^2 для любых a,bRna, b \in \mathbb{R}^n. Подставим полученное неравенство в выражение для E(xk+1x2xk)\mathbb{E}\left(\vert\vert x_{k+1} - x_\ast\vert\vert^2 \mid x_k\right), доказанное ранее:

E(14xk+1x2xk)=xkx22αxkx,f(xk)+4Lmaxα2(f(xk)f(x))+2α2σ2. \mathbb{E}\left(\left.\vphantom{\frac14}\vert\vert x_{k+1} - x_\ast\vert\vert^2\right| x_k\right) = \vert\vert x_k - x_{\ast}\vert\vert^2 - 2\alpha\langle x_k - x_{\ast}, \nabla f(x_k)\rangle + 4L_{\max}\alpha^2 \left(f(x_k) - f(x_\ast)\right) + 2\alpha^2\sigma_{\ast}^2.

Остаётся оценить скалярное произведение в правой части неравенства. Это можно сделать, воспользовавшись сильной выпуклостью функции ff: из

f(x)f(xk)+f(xk),xxk+μ2xxk2 f(x_\ast) \geq f(x_k) + \langle\nabla f(x_k), x_\ast - x_k \rangle + \frac{\mu}{2}\vert\vert x_\ast - x_k\vert\vert^2

следует

f(xk),xkxf(xk)f(x)+μ2xkx2. \langle\nabla f(x_k), x_k - x_\ast \rangle \geq f(x_k) - f(x_\ast) + \frac{\mu}{2}\vert\vert x_k - x_\ast\vert\vert^2.

Используя это неравенство в выведенной ранее верхней оценке на E(xk+1x2xk)\mathbb{E}\left(\vert\vert x_{k+1} - x_\ast\vert\vert^2 \mid x_k\right), мы приходим к следующему неравенству:

E(14xk+1x2xk)(1αμ)xkx22α(12αLmax)(f(xk)f(x))+2α2σ2(1αμ)xkx2+2α2σ2, \mathbb{E}\left(\left.\vphantom{\frac14}\vert\vert x_{k+1} - x_\ast\vert\vert^2\right| x_k\right) \leq (1-\alpha\mu)\vert\vert x_k - x_{\ast}\vert\vert^2 -2\alpha(1 - 2\alpha L_{\max})\left(f(x_k) - f(x_\ast)\right) + 2\alpha^2\sigma^2\\ \leq (1-\alpha\mu)\vert\vert x_k - x_{\ast}\vert\vert^2 + 2\alpha^2\sigma_{\ast}^2,

где в последнем неравенстве мы воспользовались неотрицательностью 2α(12αLmax)(f(xk)f(x))2\alpha(1 - 2\alpha L_{\max})\left(f(x_k) - f(x_\ast)\right), что следует из 0<α1/2Lmax0 < \alpha \leq 1/2L_{\max} и f(xk)f(x)f(x_k) \geq f(x_\ast). Действуя по аналогии с доказательством предыдущей теоремы, получаем требуемый результат.

Выводы, которые можно сделать из данной теоремы, очень похожи на те, что мы уже сделали из прошлой теоремы. Главные отличия заключаются в том, что LmaxL_{\max} может быть гораздо больше LL, т.е. максимальный допустимый размер шага α\alpha в данной теореме может быть гораздо меньше, чем в предыдущей. Однако размер окрестности теперь зависит от дисперсии стох. градиента в решении σ2\sigma_\ast^2, что может быть значительно меньше σ2\sigma^2.

Рассмотрим важный частный случай — задачи минимизации суммы функций:

minxRd{f(x)=1ni=1nfi(x)}.\min\limits_{x \in \mathbb{R}^d}\left\{f(x) = \frac{1}{n}\sum\limits_{i=1}^n f_i(x)\right\}.

Обычно fi(x)f_i(x) имеет смысл функции потерь на ii-м объекте датасета. Предположим, что fi(x)f_i(x) — выпуклая и LiL_i-гладкая функция. Тогда выполняется предположение о выпуклых гладких стохастчиеских реализациях: действительно, достаточно задать ξ\xi как случайное число из {1,2,,n}\{1,2,\ldots,n\}, имеющее равномерное распределение. Тогда справедлив результат предыдущей теоремы с Lmax=maxi1,,n)LiL_{\max} = \max_{i\in 1,\ldots,n)}L_i и σ2=1ni=1nfi(x)2\sigma_\ast^2 = \tfrac{1}{n}\sum_{i=1}^n \vert\vert\nabla f_i(x_\ast)\vert\vert^2.

Для любого K0K \ge 0 можно выбрать шаг в SGD следующим образом:

если K2Lmaxμ,γk=12Lmax,если K>2Lmaxμ и k<k0,γk=12Lmax,если K>2Lmaxμ и kk0,γk=14Lmax+μ(kk0), \text{если } K \leq \frac{2L_{\max}}{\mu}, \gamma_k = \frac{1}{2L_{\max}},\\ \text{если } K > \frac{2L_{\max}}{\mu} \text{ и } k < k_0, \gamma_k = \frac{1}{2L_{\max}},\\ \text{если } K > \frac{2L_{\max}}{\mu} \text{ и } k \geq k_0, \gamma_k = \frac{1}{4L_{\max} + \mu(k-k_0)},

где k0=K/2k_0 = \lceil K/2 \rceil. Тогда из доказанного выше результата следует (см. Лемму 3 из статьи С. Стиха), что после KK итераций

E(14xKx2)=O(Lmaxx0x2μexp(μLmaxK)+σ2μ2K). \mathbb{E}\left(\vphantom{\frac14}\vert\vert x_K - x_\ast\vert\vert^2\right) = \cal O\left(\frac{L_{\max} \vert\vert x_0 - x_\ast\vert\vert^2}{\mu}\exp\left(-\frac{\mu}{L_{\max}}K\right) + \frac{\sigma_{\ast}^2}{\mu^2 K}\right).

Таким образом, чтобы гарантировать E(14xKx2)ε\mathbb{E}\left(\vphantom{\frac14}\vert\vert x_K - x_\ast\vert\vert^2\right) \leq \varepsilon, SGD требуется

O(Lmaxμlog(Lmaxx0x2με)+σ2μ2ε) \cal O\left(\frac{L_{\max} }{\mu}\log\left(\frac{L_{\max} \vert\vert x_0 - x_\ast\vert\vert^2}{\mu\varepsilon}\right) + \frac{\sigma_{\ast}^2}{\mu^2 \varepsilon}\right)

итераций/подсчётов градиентов слагаемых. Чтобы гарантировать то же самое, градиентному спуску (GD) необходимо сделать

O(nLμlog(x0x2ε)) \cal O\left(n\frac{L}{\mu}\log\left(\frac{\vert\vert x_0 - x_\ast\vert\vert^2}{\varepsilon}\right)\right)

подсчётов градиентов слагаемых, поскольку каждая итерация GD требует nn подсчётов градиентов слагаемых (нужно вычислять полный градиент f(x)=1ni=1nfi(x)\nabla f(x) = \tfrac{1}{n}\sum_{i=1}^n \nabla f_i(x)). Можно показать, что LLmaxnLL \leq L_{\max} \leq nL, поэтому в худшем случае полученная оценка для SGD заведомо хуже, чем для GD. Однако в случае, когда Lmax=O(L)L_{\max} = \cal O(L), однозначного вывода сделать нельзя: при большом ε\varepsilon может доминировать первое слагаемое в оценке сложности SGD, поэтому в таком случае SGD будет доказуемо быстрее, чем GD (если пренебречь логарифмическими множителями).

Иными словами, чтобы достичь не очень большой точности решения, выгоднее использовать SGD, чем GD. В ряде ситуаций небольшой точности вполне достаточно, но так происходит не всегда. Поэтому возникает ествественный вопрос: можно ли так модифицировать SGD, чтобы полученный метод сходился линейно асимптотически к точному решению (а не к окрестности как SGD), но при этом стоимость его итераций была сопоставима со стоимостью итераций SGD? Оказывается, что да и соответствующие методы называются методами редукции дисперсии.

Методы редукции дисперсии

Перед тем, как мы начнём говорить о методах редукции дисперсии, хотелось бы раскрыть подробнее причину того, что SGD не сходится линейно асимптотически к точному решению. Мы рассмотрели анализ SGD в двух предположениях, и в обоих случаях нам требовалось вывести некоторую верхнюю оценку на второй момент стох. градиента, т.е. на E(gk2xk)\mathbb{E}\left(\vert\vert g_k\vert\vert^2 \mid x_k\right). В обоих случаях эта оценка содержала некоторый константный член (σ2\sigma^2 или 2σ22\sigma_\ast^2 — зависит от рассматриваемого предположения), который потом возникал и в финальной оценке на E(14xkx2)\mathbb{E}\left(\vphantom{\frac14}\vert\vert x_k - x_\ast\vert\vert^2\right), препятствуя тем самым линейно сходимости метода. Конечно, это рассуждение существенно опирается на конкретный способ анализа метода, а потому не является строгим объяснением, почему SGD не сходится линейно.

Однако важно отметить, что оценка на E(gk2xk)\mathbb{E}\left(\vert\vert g_k\vert\vert^2 \mid x_k\right) достаточно точно отражает поведение метода вблизи решения: даже если точка xkx_k оказалась по какой-то причине близка к решению xx_\ast (или даже просто совпала с решением), то E(gk2xk)\mathbb{E}\left(\vert\vert g_k\vert\vert^2 \mid x_k\right) и, в частности, E(gkf(xk)2xk)\mathbb{E}\left(\vert\vert g_k - \nabla f(x_k)\vert\vert^2 \mid x_k\right) будут порядка σ2\sigma^2 или σ2\sigma_{\ast}^2. Следовательно, при следующем шаге метод с большой вероятностью отдалится от/выйдет из решения, поскольку E(14xk+1xk2)=α2E(14gk2)α2σ2\mathbb{E}\left(\vphantom{\frac14}\vert\vert x_{k+1} - x_k\vert\vert^2\right) = \alpha^2\mathbb{E}\left(\vphantom{\frac14}\vert\vert g_k\vert\vert^2\right) \sim \alpha^2\sigma^2 или α2σ2\alpha^2\sigma_{\ast}^2.

Из приведённых выше рассуждений видно, что дисперсия стох. градиента мешает методу сходится линейно к точному решению. Поэтому хотелось бы как-то поменять правило вычисления стох. градиента, чтобы выполнялись 3 важных свойства: (1) новый стох. градиент должен быть не сильно дороже в плане вычислений, чем подсчёт стох. градиента в SGD (градиента слагаемого), (2) новый стох. градиент должен быть несмещённой оценкой полного градиента f(xk)\nabla f(x_k), и (3) дисперсия нового стох. градиента должна уменьшаться в процессе работы метода. Например, можно рассмотреть следующий стох. градиент:

gk=fjk(xk)+sk,g_k = \nabla f_{j_k}(x_k) + s_k,

где jkj_k выбирается случайно равновероятно из множества {1,2,,n}\{1, 2, \ldots, n\} и E(skxk)=0\mathbb{E}\left(s_k\mid x_k\right) = 0. В таком случае, будет выполнено свойство (2) из списка выше. Чтобы достичь желаемой цели, необходимо как-то специфицировать выбор случайного вектора sks_k. Исторически одним из первых способов выбора sks_k был sk=fjk(wk)+f(wk)s_k = -\nabla f_{j_k}(w_k) + \nabla f(w_k), где точка wkw_k обновляется раз в mnm \sim n итераций:

wk+1={wk,if k+1modm0,xk+1,if k+1modm=0. w_{k+1} = \begin{cases} w_k, & \text{if } k+1 \mod m \neq 0,\\ x_{k+1}, & \text{if } k+1 \mod m = 0. \end{cases}

Данный метод называется Stochastic Variance Reduced Gradient (SVRG). Данный методы был предложен и проанализирован в NeurIPS статье Джонсона и Жанга в 2013 году. Теперь же убедимся, что метод удовлетворяет всем трём отмеченным свойствам. Начнём с несмещённости:

gk=fjk(xk)fjk(wk)+f(wk), g_k = \nabla f_{j_k}(x_k) - \nabla f_{j_k}(w_k) + \nabla f(w_k),

E(gkxk)=1ni=1n(fi(xk)fi(wk)+f(wk))=f(xk). \mathbb{E}\left(g_k\mid x_k\right) = \frac{1}{n}\sum\limits_{i=1}^n \left(\nabla f_{i}(x_k) - \nabla f_{i}(w_k) + \nabla f(w_k)\right) = \nabla f(x_k).

Далее, вычисление gkg_k подразумевает 2 подсчёта градентов слагаемых при kmodm0k \mod m \neq 0 и n+2n+2 подсчёта градентов слагаемых при kmodm0k \mod m \neq 0. Таким образом, за mm последователльных итераций SVRG происходит вычисление 2(m1)+n+2=2m+n2(m-1) + n + 2 = 2m + n градиентов слагаемых, в то время как SGD требуется mm подсчётов градиентов слагаемых. Если m=nm = n (стандартный выбор параметра mm), то nn итераций SVRG лишь в 3 раза дороже, чем nn итераций SGD. Иными словами, в среднем итерация SVRG не сильно дороже итерации SGD.

Наконец, если мы предположим, что метод сходится E(14xkx2)0\mathbb{E}\left(\vphantom{\frac14}\vert\vert x_k - x_\ast\vert\vert^2\right) \to 0 (а он действительно сходится, см., например, доказательство вот тут), то получим, что E(14wkx2)0\mathbb{E}\left(\vphantom{\frac14}\vert\vert w_k - x_\ast\vert\vert^2\right) \to 0, а значит E(14xkwk2)0\mathbb{E}\left(\vphantom{\frac14}\vert\vert x_k - w_k\vert\vert^2\right) \to 0 и E(14f(wk)2)0\mathbb{E}\left(\vphantom{\frac14}\vert\vert\nabla f(w_k)\vert\vert^2\right) \to 0. Но тогда в силу Липшицевости градиентов fif_i для всех i=1,,ni=1,\ldots,n имеем:

E(14gk2)=E(14fjk(xk)fjk(wk)+f(wk)2)2E(14fjk(xk)fjk(wk)2)+2E(14f(wk)2)2LmaxE(14xkwk2)+2E(14f(wk)2)0, \mathbb{E}\left(\vphantom{\frac14}\vert\vert g_k\vert\vert^2\right) = \mathbb{E}\left(\vphantom{\frac14}\vert\vert\nabla f_{j_k}(x_k) - \nabla f_{j_k}(w_k) + \nabla f(w_k)\vert\vert^2\right)\\ \leq 2\mathbb{E}\left(\vphantom{\frac14}\vert\vert\nabla f_{j_k}(x_k) - \nabla f_{j_k}(w_k)\vert\vert^2\right) + 2\mathbb{E}\left(\vphantom{\frac14}\vert\vert\nabla f(w_k)\vert\vert^2\right)\\ \leq 2L_{\max} \mathbb{E}\left(\vphantom{\frac14}\vert\vert x_k - w_k\vert\vert^2\right) + 2\mathbb{E}\left(\vphantom{\frac14}\vert\vert\nabla f(w_k)\vert\vert^2\right) \to 0,

а значит, дисперсия gkg_k стремится к нулю.

Приведённые выше рассуждения не являются формальным доказательством сходимости метода, но частично объясняют, почему метод сходится и, самое главное, объясняют интуицию позади формул, задающих метод. Строгое доказательство можно прочитать вот тут. Мы же здесь приведём результат о сходимости немного другого метода — Loopless Stochastic Variance Reduced Gradient (L-SVRG), который был предложен в 2015 году и переоткрыт в 2019 году. Основное отличие от SVRG состоит в том, что точка wkw_k теперь обновляется на каждой итерации с некоторой маленькой вероятностью p1/np \sim 1/n:

wk+1={wk,с вероятностью 1p,xk,с вероятностью p. w_{k+1} = \begin{cases} w_k, & \text{с вероятностью } 1-p,\\ x_{k}, & \text{с вероятностью } p. \end{cases}

Иными словами, L-SVRG имеет случайную длину цикла, в котором wkw_k не обновляется. Вся интуиция и все наблюдения приведённые для SVRG выше, справедливы и для L-SVRG.

Можно доказать следующий результат.

Теорема. Предположим, что ff является LL-гладкой, μ\mu-сильно выпуклой и имеет вид суммы, функции fif_i являются выпуклыми и LiL_i-гладкими для всех i=1,,ni=1,\ldots, n, и размер шага удовлетворяет 0<α1/6Lmax0 < \alpha \leq 1/6L_{\max}, где Lmax=maxi1,,nLiL_{\max} = \max_{i\in 1,\ldots,n} L_{i}. Тогда для всех k0k \geq 0 для итераций L-SVRG выполняется неравенство

E(14xkx2)(1min{αμ,p2})kV0, \mathbb{E}\left(\vphantom{\frac14}\vert\vert x_k - x_{\ast}\vert\vert^2\right) \leq \left(1 - \min\left\{\alpha\mu, \frac{p}{2}\right\}\right)^kV_0,

где V0=x0x2+4α2pσ02V_0 = \vert\vert x_0 - x_\ast\vert\vert^2 + \tfrac{4\alpha^2}{p}\sigma_0^2, σ02=1ni=1nfi(x0)fi(x)\sigma_0^2 = \tfrac{1}{n}\sum_{i=1}^n \vert\vert\nabla f_i(x_0) - \nabla f_i(x_\ast)\vert\vert.

Замечание. В частности, если α=1/6Lmax\alpha = 1/6L_{\max} и p=1/np = 1/n, то

E(14xkx2)(1min{μ6Lmax,12n})kV0. \mathbb{E}\left(\vphantom{\frac14}\vert\vert x_k - x_{\ast}\vert\vert^2\right) \leq \left(1 - \min\left\{\frac{\mu}{6L_{\max}}, \frac{1}{2n}\right\}\right)^kV_0.

Следовательно, чтобы гарантировать E(14xkx2)ε\mathbb{E}\left(\vphantom{\frac14}\vert\vert x_k - x_\ast\vert\vert^2\right) \leq \varepsilon, L-SVRG требуется

O((n+Lmaxμ)log(V0ε)) \cal O\left(\left(n + \frac{L_{\max} }{\mu}\right)\log\left(\frac{V_0}{\varepsilon}\right)\right)

итераций/подсчётов градиентов слагаемых (в среднем). Напомним, что чтобы гарантировать то же самое, градиентному спуску (GD) необходимо сделать

O(nLμlog(Lx0x2με)) \cal O\left(n\frac{L}{\mu}\log\left(\frac{L \vert\vert x_0 - x_\ast\vert\vert^2}{\mu\varepsilon}\right)\right)

подсчётов градиентов слагаемых, поскольку каждая итерация GD требует nn подсчётов градиентов слагаемых (нужно вычислять полный градиент f(x)=1ni=1nfi(x)\nabla f(x) = \tfrac{1}{n}\sum_{i=1}^n \nabla f_i(x)). Можно показать, что LLmaxnLL \leq L_{\max} \leq nL, поэтому в худшем случае полученная оценка для L-SVRG не лучше, чем для GD. Однако в случае, когда Lmax=O(L)L_{\max} = \cal O(L), L-SVRG имеет сложность значительно лучше, чем GD (если пренебречь логарифмическими множителями).

В заключение этого раздела, хотелось бы отметить, что существуют и другие методы редукции дисперсии. Одним из самых популярных среди них является SAGA. В отличие от SVRG/L-SVRG, в методе SAGA хранится набор градиентов f1(wk1),f2(wk2),,fn(wkn)\nabla f_1(w_k^1), \nabla f_2(w_k^2), \ldots, \nabla f_n(w_k^n). Здесь точка wkiw_k^i обозначает точку, в которой в последний раз был подсчитан градиент функции ii до итерации kk. Формально это можно записать следующим образом:

w01=w02==w0n, w_0^1 = w_0^2 = \ldots = w_0^n,

gk=fjk(xk)fjk(wkjk)+1ni=1nfi(wki), g_k = \nabla f_{j_k}(x_k) - \nabla f_{j_k}(w_k^{j_k}) + \frac{1}{n}\sum\limits_{i=1}^n \nabla f_{i}(w_k^{i}),

wk+1jk=xk,wk+1i=wki для всех ijk, w_{k+1}^{j_k} = x_k, \quad w_{k+1}^i = w_k^i \text{ для всех } i \neq j_k,

xk+1=xkαgk. x_{k+1} = x_k - \alpha g_k.

Основное преимущество SAGA состоит в том, что не требуется вычислять полный градиент всей суммы по ходу работы метода, однако в начале требуется посчитать градиенты всех слагаемых (отмечаем здесь, что эта операция может быть гораздо дороже по времени, чем вычисление полного градиента) и, более того, требуется хранить nn векторов, что может быть недопустимо для больших датасетов. В плане теоретических гарантий SAGA и L-SVRG не отличимы.

Ниже приведён график с траекториями SGD (с постоянным шагом), L-SVRG и SAGA при решении задачи логистической регрессии. Как можно видеть из графика, SGD достаточно быстро достигает не очень высокой точности и начинает осциллировать вокруг решения. В то же время, L-SVRG и SAGA достигают той же точности медленнее, но зато не осциллируют вокруг решения, а продолжают сходится (причём линейно).

Сравнение работы SGD, L-SVRG и SAGA при решении задачи логистической регрессии на датасете gisette из библиотеки LIBVSM.

Shodimost

Чтобы добавить в заметки выделенный текст, нажмите Command + E

Пройдите квиз по параграфу

Чтобы закрепить пройденный материал
Предыдущий параграф14.3. Методы второго порядка

От метода Ньютона до LBFGS

Следующий параграф15.1. Введение в онлайн-обучение